Combinations

Time: O(O(KxC(N,K))); Space: O(K); medium

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example 1:

Input: n = 4, k = 2

Output:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

[2]:

class Solution1(object):
    """
    Time: O(K*C(N,K))
    Space: O(K)
    """
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        result, combination = [], []
        i = 1
        while True:
            if len(combination) == k:
                result.append(combination[:])
            if len(combination) == k or \
               len(combination)+(n-i+1) < k:
                if not combination:
                    break
                i = combination.pop()+1
            else:
                combination.append(i)
                i += 1
        return result

[5]:

s = Solution1()
n = 4
k = 2
# print(s.combine(n, k))
assert s.combine(n, k) == [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
# assert s.combine(n, k) == [
#   [2,4],
#   [3,4],
#   [2,3],
#   [1,2],
#   [1,3],
#   [1,4],
# ]

2. DFS

[6]:

class Solution2(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        def combineDFS(n, start, intermediate, k, result):
            if k == 0:
                result.append(intermediate[:])
                return
            for i in range(start, n):
                intermediate.append(i+1)
                combineDFS(n, i+1, intermediate, k-1, result)
                intermediate.pop()

        result = []
        combineDFS(n, 0, [], k, result)
        return result

[8]:

s = Solution2()
n = 4
k = 2
assert s.combine(n, k) == [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
# assert s.combine(n, k) == [
#   [2,4],
#   [3,4],
#   [2,3],
#   [1,2],
#   [1,3],
#   [1,4],
# ]